﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions.Problems
{
    /*
     * The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23 × 32 × 7, so rad(504) = 2 × 3 × 7 = 42.

If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n), and sorting on n if the radical values are equal, we get:


Let E(k) be the kth element in the sorted n column; for example, E(4) = 8 and E(6) = 9.

If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).

     * */
    class Problem124 : IProblem
    {
        public string Calculate()
        {
            int limit = 100000;
            int find = 10000;

            Dictionary<int, int> rad = new Dictionary<int, int>();

            long[] p = new long[limit];
            p[0] = 2;

            SieveOfAtkin sieve = new SieveOfAtkin(limit * 10);
            for (int i = 1, j = 3; i < p.Length; i++)
            {
                while (!sieve.IsPrime(j))
                    j += 2;
                p[i] = j;
                j += 2;
            }

            rad.Add(1, 1);

            for (int n = 2; n <= limit; n++)
            {
                if (sieve.IsPrime(n))
                {
                    rad.Add(n, n);
                }
                else
                {
                    long product = 1;
                    for (int i = 0; i < p.Length && p[i] < n; i++)
                    {
                        if (n % p[i] == 0)
                            product *= p[i];
                    }
                    rad.Add(n, (int)product);
                }
            }

            int result = rad.OrderBy(x => x.Value).ElementAt(find - 1).Key;

            return result.ToString();
        }
    }
}
